import java.util.*;

public class BinaryTree {
        public static class BTNode {
            BTNode left;
            BTNode right;
            int val;

            BTNode(int value) {
                this.val = value;
            }
        }
        private BTNode root;
    public BTNode createBinaryTree(){
        BTNode node1 = new BTNode(1);
        BTNode node2 = new BTNode(2);
        BTNode node3 = new BTNode(3);
        BTNode node4 = new BTNode(4);
        BTNode node5 = new BTNode(5);
        BTNode node6 = new BTNode(6);
        root = node1;
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node5.right = node6;
        return node1;
    }
    public int getHeight(BTNode root){
        //求二叉树的高度
        //左右树最大值
        if(root == null){
            return 0;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return left > right?left+1:right+1;
    }
    // 检测值为value的元素是否存在
    BTNode find(BTNode root, int val){

        if(root == null || root.val == val){
            return root;
        }
        BTNode left = find(root.left,val);
        if(left != null){
            return left;
        }
        return find(root.right,val);
    }
    //层序遍历
    void levelOrder(BTNode root){
        //采用队列
        Queue<BTNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            BTNode btNode = queue.poll();
            System.out.printf("%d ",btNode.val);
            if(btNode.left != null)
                queue.offer(btNode.left);
            if(btNode.right != null)
                queue.offer(btNode.right);
        }
    }
    public List<List<Integer>> levelOrder1(BTNode root) {
        List<List<Integer>> list = new LinkedList<>();
        Queue<BTNode> queue = new LinkedList<>();
        queue.offer(root);
        //如何分层
        if(root == null){
            return list;
        }
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> lists = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                BTNode btNode = queue.poll();
                lists.add(btNode.val);
                if(btNode.left != null)
                    queue.offer(btNode.left);
                if(btNode.right != null)
                    queue.offer(btNode.right);
            }
            list.add(lists);

        }
        return list;
    }
    //判断二叉树是否完全相同
    public boolean isSameTree(BTNode p, BTNode q) {
        //找出相同的情况
        if(p == null && q == null){
            return true;
        }
        if(p == null || q == null){
            return false;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);

    }
    //另一棵树的子树
    public boolean isSubtree(BTNode root, BTNode subRoot) {
        //判断subRoot是不是root的子树
        //1.当根相同的时候开始同时遍历，
        if(root == null){
            return false;
        }
        if(root.val == subRoot.val){
            //开始同时遍历
            //判断二叉树是否完全相等
            if(isSameTree(root,subRoot)){
                //如果完全相同就是他的子树，就可以直接返回true
                return true;
            }
        }
        boolean t1 = isSubtree(root.left,subRoot);
        if(t1){
            return true;
        }

        return isSubtree(root.right,subRoot);
    }
    //翻转二叉树
    public BTNode invertTree(BTNode root) {
        //交换节点，按照前序遍历方式
        invertTree1(root);
        return root;
    }
    //负责遍历
    public void invertTree1(BTNode root) {
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null)
            return;
        swap(root);
        invertTree1(root.left);
        invertTree1(root.right);
    }
    //负责交换
    public void swap(BTNode root) {

        BTNode btNode = root.left;
        root.left = root.right;
        root.right = btNode;
    }
    //如何利用反转二叉树的返回值

    //对称二叉树
    public boolean isSymmetric(BTNode root) {
        //一个前序遍历，一个后续遍历
        if(root == null){
            return false;
        }
      return  isSymmetricC(root.left,root.right);
    }

    public boolean isSymmetricC(BTNode rootLeft,BTNode rootRight) {
        if(rootLeft == null && rootRight == null){
            return true;
        }
        if(rootLeft == null ||rootRight == null){
            return false;
        }
        if(rootLeft.val != rootRight.val){
            return false;
        }
        return isSymmetricC(rootLeft.left,rootRight.right)&&
                isSymmetricC(rootLeft.right,rootRight.left);

    }
}
